1. Field of the Invention
This invention relates generally to computing, and in particular to quantum computation.
2. Description of the Related Art
A quantum computer solves computational problems by performing physical transformations upon a finite quantum mechanical system in order to force the system to occupy a state with desired properties. Rather than operating on classical bits, which must take on values of 1 or 0 deterministically, a quantum computer operates on quantum mechanical “qubits,” which can exist in arbitrary superpositions of two states. It is known that a quantum computer can solve some computational problems—not least of which, the simulation of other quantum systems—much faster than its classical counterpart. However, the class of problems for which significant speedup is possible is not yet known.
The 3 variable per clause boolean satisfiability problem, or 3SAT, consists of assigning a set of boolean variables x1, x2, x3 . . . to be true or false in such a way that a propositional logic formula in conjunctive normal form, or “CNF”,(xx2x4)(x2x3x5)  (1)evaluates to true. Here, variables (xn) or their negations (xn) within the same clause are linked with an OR () operator, while different clauses are linked by an AND () operator. An assignment must satisfy all clauses in order to solve the problem.
3SAT is well known in computer science for being NP complete [8, 4]. This means that it has the property that any problem whose solutions can be checked in polynomial time (class “NP”) can be reduced in polynomial time to a 3SAT problem. Thus, a polynomial time solution for 3SAT could be used to solve any problem in NP in polynomial time as well. It is believed but not proven that no algorithm on a classical computer can solve an NP complete problem in polynomial time; the question of whether this is true is one of the most famous problems in mathematics [3].
Here reduction consists of a mapping from an instance of one problem to an instance of another, in such a way that a solution to the second instance can be mapped to a solution of the first. A computational problem consists of a list of problem parameters, plus a statement of what properties a solution to the problem must satisfy [4]. An instance of a problem is obtained by specifying particular values for all problem parameters.
A solution algorithm for a computational problem determines whether a particular instance has a solution or proves that none exists, but does not necessarily produce a solution. A constructive solution algorithm produces at least one valid solution, provided that some solution exists. A probabilistic solution algorithm determines whether a solution exists or not with probability of error no greater than some value ∈ between 0 and ½, which by convention is usually chosen to be ⅓. A probabilistic algorithm can be run many times to increase the certainty that a given instance either has or does not have a solution.